import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 晓星航
 * Date: 2023-04-13
 * Time: 8:20
 */


class Card implements Comparable<Card>{
    public int rank; // 数值
    public String suit; // 花色
    public Card(int rank, String suit) {
        this.rank = rank;
        this.suit = suit;
    }
    //ctrl + i 快速实现接口
    @Override
    public int compareTo(Card o) {
        return this.rank - o.rank;
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        //getClass() != o.getClass() 比较的是：是不是同一个类型
        if (o == null || getClass() != o.getClass()) {
            return false;
        }
        Card card = (Card) o;
        return rank == card.rank && Objects.equals(suit,card.suit);
    }

    @Override
    public String toString() {
        return "Card{" +
                "rank=" + rank +
                ", suit='" + suit + '\'' +
                '}';
    }
}
class RankComparator implements Comparator<Card> {

    @Override
    public int compare(Card o1, Card o2) {
        return o1.rank - o2.rank;
    }
}
public class TestDemo {
    /**
     * 时间复杂度：O(N^2)
     *      最好的情况时O(N)：对于直接插入排序来说，最好的情况就是数据有序时
     *      根据这个结论，推导出另一个结论：对于直接插入排序来说，数据越有序，越快。
     * 空间复杂度：O(1)
     * 稳定性：稳定的
     * 一个稳定的排序，可以实现为不稳定的排序
     * 但是一个本身就不稳定的排序，是不能变为稳定的排序
     * 经常使用在  数据量不多    且 整体数据 趋于有序了
     * @param array
     */
    public static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= 0 ; j--) {
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
                    //array[j + 1] = tmp;  只要j回退的时候，遇到了 比tmp小的元素就结束这次的比较
                    break;
                }
            }
            //j回退到了 小于0 的地方
            array[j + 1] = tmp;
        }
    }

    /**
     *
     * @param array 待排序序列
     * @param gap 数组
     */
    public static void shell(int[] array, int gap) {
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i - gap;
            for (; j >= 0; j-=gap) {
                if (array[j] > tmp) {
                    array[j + gap] = array[j];
                } else {
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }

    /**
     * 时间复杂度[和增量有关系]：O(n^1.3 - n^1.5)
     * 空间复杂度：O(1)
     * 稳定性：不稳定的
     *   看在比较的过程中  是否发生了跳跃式的交换  如果发生了跳跃式的交换 那么就是不稳定的排序
     * 基本上没有考过
     * @param array 待排序的序列
     */
    public static void shellSort(int[] array) {
        int gap = array.length;
        while (gap > 1) {
            shell(array,gap);
            gap /= 2;
        }
        shell(array,1);//保证最后是一组
    }
    public static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    /**
     * 选择排序
     * 时间复杂度：O(N^2)
     * 空间复杂度：O(1)
     * 稳定性：不稳定的排序
     * @param array 待排序的序列
     */
    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            swap(array,i,minIndex);
        }
    }

    /**
     *时间复杂度：O(N * log N)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array
     */
    public static void heapSort(int[] array) {
        //1/建堆O(N)
        createHeap(array);
        int end = array.length - 1;
        //2、交换然后调整 O(N * log N)
        while (end > 0) {
            swap(array,0,end);
            shiftDown(array,0,end);
            end--;
        }
    }
    public static void createHeap(int[] array) {
        for (int parent = (array.length-1-1)/2; parent >= 0; parent--) {
            shiftDown(array,parent,array.length);
        }
    }
    public static void shiftDown(int[] array,int parent,int len) {
        int child = parent * 2 + 1;//左孩子下标
        while (child < len) {
            if (child + 1 < len && array[child] < array[child + 1]) {
                child++;
            }
            //child下标 就是左右孩子最大值的下标
            if (array[parent] < array[child]) {
                swap(array,parent,child);
                parent = child;
                child = parent * 2 + 1;
            } else {
                break;
            }
        }
    }
    public static void main8(String[] args) {
        int[] array = {12,5,8,13,29,3,27,19,12,0,14,25,42,2,7};
        heapSort(array);
        System.out.println(Arrays.toString(array));
    }
    /**
     * 有序的数据
     * @param capacity
     */
    public static void test1(int capacity) {
        int[] array = new int[capacity];
        for (int i = 0; i < array.length; i++) {
            array[i] = i;
        }
        long start = System.currentTimeMillis();
//        insertSort(array);
//        shellSort(array);
//        selectSort(array);
        heapSort(array);
        long end = System.currentTimeMillis();
        System.out.println(end - start);
    }

    /**
     * 无序的数据
     * @param capacity
     */
    public static void test2(int capacity) {
        int[] array = new int[capacity];
        Random random = new Random();
        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextInt(capacity);
        }
        long start = System.currentTimeMillis();
//        insertSort(array);
//        shellSort(array);
//        selectSort(array);
        heapSort(array);
        long end = System.currentTimeMillis();
        System.out.println(end - start);
    }
    public static void main(String[] args) {
        test1(10_0000);

        test2(10_0000);
    }

    public static void main6(String[] args) {
        int[] array = {12,5,8,13,29,3,4,23,14,25,42,2,7};
        selectSort(array);
        System.out.println(Arrays.toString(array));
    }
    public static void main5(String[] args) {
        int[] array = {12,5,8,13,29,3,4,23,14,25,42,2,7};
        shellSort(array);
        System.out.println(Arrays.toString(array));
    }
    public static void main4(String[] args) {
        int[] array = {12,5,8,13,29,3,4};
        insertSort(array);
        System.out.println(Arrays.toString(array));
    }
    public static void main3(String[] args) {
        Card card1 = new Card(1,"♥");
        Card card2 = new Card(2,"♥");
        PriorityQueue<Card> priorityQueue = new PriorityQueue<>(new Comparator<Card>() {
            @Override
            public int compare(Card o1, Card o2) {
                return o1.rank - o2.rank;
            }
        });
        priorityQueue.offer(card1);//直接放到了Queue数组的0下标
        priorityQueue.offer(card2);
        System.out.println(priorityQueue);
        System.out.println(card1.equals(card2));
    }
    public static void main2(String[] args) {
        PriorityQueue<Card> priorityQueue = new PriorityQueue<>();
        Card card1 = new Card(1,"♥");
        Card card2 = new Card(2,"♥");
        System.out.println(card1.compareTo(card2));//大于返回1 等于返回0 小于返回-1

    }
    public static void main1(String[] args) {
        PriorityQueue<Card> priorityQueue = new PriorityQueue<>();
        priorityQueue.offer(new Card(2,"♥"));//直接放到了Queue数组的0下标
        priorityQueue.offer(new Card(1,"♥"));
        priorityQueue.offer(new Card(3,"♥"));
        System.out.println(priorityQueue);

    }
}
